package leetcode_day._2021._202111;

import java.util.Random;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/11/22 14:52
 * 打乱数组
 * 给你一个整数数组 nums ，设计算法来打乱一个没有重复元素的数组。
 * 实现 Solution class:
 *   Solution(int[] nums) 使用整数数组 nums 初始化对象
 *   int[] reset() 重设数组到它的初始状态并返回
 *   int[] shuffle() 返回数组随机打乱后的结果
 * 算法：洗牌算法
 * 对于下标 x 而言，从 [x, n - 1] 中随机选出一个位置与 x 进行交换
 * 所有的位置都这样处理
 */
public class _22_384 {

    class Solution {
        int[] nums;
        int n;
        Random random = new Random();

        public Solution(int[] nums) {
            this.nums = nums;
            this.n = nums.length;
        }

        public int[] reset() {
            return nums;
        }

        public int[] shuffle() {
            int[] ans = nums.clone();
            for (int i = 0; i < n; i++) swap(ans, i, i + random.nextInt(n - i));
            return ans;
        }
        void swap(int[] nums, int i, int j) {
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
    }

}
